Graph / Dominating set (Bibtex)

P240: Enumeration of all minimal dominating sets in a graph

Input:

A graph $G = (V, E)$.

Output:

All minimal dominating sets in $G$.

Complexity:

$O(1.7159^{|V|})$ total time.

Comment:

Reference:

[Fomin2008] (Bibtex)

P228: Enumeration of $z$ smallest weighted edge dominating sets in a graph

Input:

An weighted graph $G = (V, E)$, and positive integers $k$ and $z$. Each edge of $G$ has a positive weight.

Output:

$z$ smallest weighted edge dominating sets in $G$.

Complexity:

$O(5.6^{2k}k^4z^2 +4^{2k}k^3z|V|)$ total time.

Comment:

Reference:

[Wang2009] (Bibtex)

P454: Enumerate all minimal dominating sets in a strongly chordal graph.

Input:

A strongly chordal graph $G$.

Output:

All minimal dominating sets in $G$.

Complexity:

Polynomial delay.

Comment:

Reference:

[Kante2011] (Bibtex)

P455: Enumerate all minimal dominating sets in a graph with bounded degeneracy.

Input:

A graph $G$ with bounded degeneracy.

Output:

All minimal dominating sets in $G$.

Complexity:

Polynomial delay.

Comment:

Reference:

[Kante2011] (Bibtex)

P456: Enumerate all minimal dominating sets in a split graph

Input:

A split graph $G = (V, E)$.

Output:

All minimal dominating sets in $G$.

Complexity:

$O(|V| + |E|)$ delay with $O(|V|^2)$ space.

Comment:

Reference:

[Kante2011] (Bibtex)

P202: Enumeration of all minimal dominating sets in a line graph

Input:

A line graph $G$.

Output:

All minimal dominating sets in $G$.

Complexity:

$O(||G||^5N^6)$ total time.

Comment:

$||G||$ is the size of $G$ and $N$ is the number of minimal dominating sets in $G$.

Reference:

[Kante2012] (Bibtex)

P203: Enumeration of all minimal dominating sets in a path graph or $(C_4, C_5, craw)$-free graph

Input:

A line graph or $(C_4, C_5, craw)$-free graph $G$.

Output:

All minimal dominating sets in $G$.

Complexity:

$O(||G||^2N^3)$ total time.

Comment:

$||G||$ is the size of $G$ and $N$ is the number of minimal dominating sets in $G$.

Reference:

[Kante2012] (Bibtex)

P204: Enumeration of all minimal edge-dominating sets in a graph

Input:

A graph $G$.

Output:

All minimal edge-dominating sets in $G$.

Complexity:

$O(||L(G)||^5N^6)$ total time.

Comment:

$L(G)$ is the line graph of $G$, $||L(G)||$ is the size of $L(G)$, and $N$ is the number of minimal edge-dominating sets in $G$.

Reference:

[Kante2012] (Bibtex)

P35: Enumeration of all minimal dominating sets in an undirected permutation graph

Input:

An undirected permutation graph $G=(V, E)$.

Output:

All minimal dominating sets.

Complexity:

$O(|V|)$ delay with $O(|V|^8)$ pre-processing.

Comment:

Reference:

[Kante2013] (Bibtex)

P36: Enumeration of all minimal dominating sets in an undirected interval graph

Input:

An undirected interval graph $G=(V, E)$.

Output:

All minimal dominating sets.

Complexity:

$O(|V|)$ delay with $O(|V|^3)$ pre-processing.

Comment:

Reference:

[Kante2013] (Bibtex)

P124: Enumeration of all minimal edge dominating sets in a graph

Input:

A graph $G = (V, E)$.

Output:

All minimal edge dominating sets in $G$.

Complexity:

$O(|V|^6|\mathcal{L}|)$ delay.

Comment:

$\mathcal{L}$ is the set of already generated solutions.

Reference:

[Golovach2013a] (Bibtex)

P125: Enumeration of all minimal dominating sets in a line graph

Input:

A line graph $G = (V, E)$.

Output:

All minimal dominating sets in $G$.

Complexity:

$O(|V|^2|E|^2|\mathcal{L}|)$ delay.

Comment:

$\mathcal{L}$ is the set of already generated solutions.

Reference:

[Golovach2013a] (Bibtex)

P126: Enumeration of all minimal edge dominating sets in a bipartite graph

Input:

A bipartite graph $G = (V, E)$.

Output:

All minimal edge dominating sets in $G$.

Complexity:

$O(|V|^4|\mathcal{L}|)$ delay.

Comment:

$\mathcal{L}$ is the set of already generated solutions.

Reference:

[Golovach2013a] (Bibtex)

P127: Enumeration of all minimal dominating sets in the line graph of a bipartite graph

Input:

A graph $G = (V, E)$.

Output:

All minimal dominating sets in $G$.

Complexity:

$O(|V|^2|E||\mathcal{L}|)$ delay.

Comment:

$\mathcal{L}$ is the set of already generated solutions.

Reference:

[Golovach2013a] (Bibtex)

P128: Enumeration of all minimal dominating sets in a graph of girth at least 7

Input:

A graph $G = (V, E)$ of girth at least 7.

Output:

All minimal dominating sets in $G$.

Complexity:

$O(|V|^2|E||\mathcal{L}|^2)$ delay.

Comment:

$\mathcal{L}$ is the set of already generated solutions.

Reference:

[Golovach2013a] (Bibtex)

P189: Enumeration of all 2-dominating sets in a tree

Input:

A tree $T = (V, E)$.

Output:

All 2-dominating sets of $T$.

Complexity:

$O(1.3248^n)$ total time.

Comment:

If a subset $U\subseteq V$ is a 2-dominating set if every vertex $v \in V \setminus U$ has at least two neighbors in $U$.

Reference:

[Krzywkowski2013] (Bibtex)

P457: Enumerate all minimal dominating sets in a chordal graph.

Input:

A chordal graph $G = (V, E)$.

Output:

All minimal dominating sets in $G$.

Complexity:

$O(1.6181^{|V|})$ total time.

Comment:

Reference:

[Couturier2013a] (Bibtex)

P458: Enumerate all minimal dominating sets in a split graph.

Input:

A split graph $G = (V, E)$.

Output:

All minimal dominating set in $G$.

Complexity:

$O(1.4656^{|V|})$ total time.

Comment:

Reference:

[Couturier2013a] (Bibtex)

P459: Enumerate all minimal dominating sets in a proper interval graph.

Input:

A proper interval graph $G = (V, E)$.

Output:

All minimal dominating sets in $G$.

Complexity:

$O(1.4656^{|V|})$ total time.

Comment:

Reference:

[Couturier2013a] (Bibtex)

P460: Enumerate all minimal dominating sets in a cograph

Input:

A cograph $G=(V, E)$.

Output:

All minimal dominating sets in $G$.

Complexity:

$O^*(15^{|V|/6})$ total time.

Comment:

There is a cograph with $O(15^{|V|/6})$ minimal dominating sets.

Reference:

[Couturier2013a] (Bibtex)

P461: Enumerate all minimal dominating sets in a trivially perfect graph.

Input:

Trivially perfect graph $G = (V, E)$.

Output:

All minimal dominating sets in $G$.

Complexity:

$O^*(3^{|V|/3})$ total time.

Comment:

There is a trivially perfect graphs with $3^{|V|/3}$ minimal dominating sets

Reference:

[Couturier2013a] (Bibtex)

P462: Enumerate all minimal dominating sets in a threshold graph.

Input:

A threshold graph $G = (V, E)$.

Output:

All minimal dominating sets in $G$.

Complexity:

$O(|V|^2)$ total time.

Comment:

A threshold graph has exactly $\omega(G)$ minimal dominating sets, where $\omega(G)$ is the size of maximum clique in $G$.

Reference:

[Couturier2013a] (Bibtex)

P463: Enumerate all minimal dominating sets in a chain graph.

Input:

A chain graph $G =(V, E)$.

Output:

All minimal dominating sets in $G$.

Complexity:

$O(|V||E|)$ total time.

Comment:

Reference:

[Couturier2013a] (Bibtex)

P347: Enumeration of all minimal dominating sets in a $P_6$-free chordal graph

Input:

A $P_6$-free chordal graph $G = (V, E)$.

Output:

All minimal dominating sets in $G$.

Complexity:

Linear delay with $O(|V|^2)$ space.

Comment:

Reference:

[Kante2014] (Bibtex)

P424: Enumeration of all minimal dominating sets in a chordal bipartite graph

Input:

A chordal bipartite graph $G$.

Output:

All minimal dominating sets in $G$.

Complexity:

$O(n^3m|\mathcal{L}|^2)$ delay and the total running time is $O(n^3m|\mathcal{L}^*|^2)$.

Comment:

$n$ is the number vertices in $G$, $m$ is the number of edges in $G$, $\mathcal{L}$ is the family of already generated minimal dominating sets, and $\mathcal{L}^*$ is the family of all minimal dominating sets.

Reference:

[Golovach2015] (Bibtex)

P502: Enumerate all minimal dominating sets in a triangle-free graph.

Input:

A triangle-free graph $G$ with $n$ vertices.

Output:

All minimal dominating sets in $G$.

Complexity:

$O(poly(n)\cdot |\mathcal{D}(G)|^2)$ total time with $O(poly(n))$ space.

Comment:

$\mathcal{D}(G)$ is the set of solutions.

Reference:

[Bonamy2019] (Bibtex)